package leetcode; /**
 * description:
 * author:张腾
 * date:2021-07-27
 */

import java.util.ArrayDeque;

/**
 * 给你一个整数数组 nums ，数组中共有 n 个整数。132 模式的子序列 由三个整数 nums[i]、nums[j] 和 nums[k] 组成，并同时满足：i < j < k 和 nums[i] < nums[k] < nums[j] 。
 *
 * 如果 nums 中存在 132 模式的子序列 ，返回 true ；否则，返回 false 。
 */
public class leetcode456 {
    public boolean find132pattern(int[] nums) {
        //栈中保存132中的3，即数组中大于k的数
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        //k表示132中的2，要使得k在小于132中的3的前提下尽可能地大，这样数组中满足132中的1的概率也会大
        int k = Integer.MIN_VALUE;
        for (int i = nums.length - 1; i > 0; i--) {
            if (nums[i]<k) return true;
            //如果当前数字比栈中数字大，则弹出栈中数字来替换k（因为栈中数字一定大于等于k），再将该数字压入栈作为3
            //如果小于栈中数字，则直接压入栈中
            while (!stack.isEmpty() && stack.peekLast()<nums[i]) {
                //k尽可能大
                k = Math.max(k,stack.pollLast());
            }
            stack.addLast(nums[i]);
        }
        return false;
    }
}
